home *** CD-ROM | disk | FTP | other *** search
/ Hyper Stacks 1994 May / Hyper Stacks (Pacific HiTech)(1994)[Mac].iso / Reference / Abstracts of CSLI Reports / Abstracts of CSLI Reports / card_26071.txt < prev    next >
Encoding:
Text File  |  1988-05-17  |  2.3 KB  |  59 lines

  1. -- card: 26071 from stack: in
  2. -- bmap block id: 0
  3. -- flags: 4000
  4. -- background id: 5371
  5. -- name: 
  6.  
  7.  
  8. -- part contents for background part 5
  9. ----- text -----
  10. Report No. CSLI-87-82
  11.  
  12. -- part contents for background part 6
  13. ----- text -----
  14. Final Algebras, Cosemicomputable
  15. Algebras, and Degrees of Unsolvability
  16. ____________
  17.  
  18. -- part contents for background part 7
  19. ----- text -----
  20.  
  21. Lawrence Moss, Jos√©  Meseguer, and Joseph A. Goguen
  22.  
  23. -- part contents for background part 8
  24. ----- text -----
  25.  
  26. Final Algebras, Cosemicomputable  
  27.    Algegras, and Degrees of Unsolvability 
  28. Lawrence S. Moss, Jose Meseguer, and 
  29. Joseph A. Goguen
  30.  
  31. This paper studies some computability notions for abstract data types, and in particular compares cosemicomputable many-sorted algebras with a notion of finality to model minimal-state realiza-tions of abstract (software) machines. Given a finite many-sorted signature √ç 
  32. and a set V of visible sorts, for every √ç-algebra A with co-r.e. behavior and nontrivial, computable V-behavior, there is a finite signature extension √ç' of √ç
  33. (without new sorts) and finite set E of
  34. √ç'-equations such that A is isomorphic 
  35.  
  36. -- part contents for background part 14
  37. ----- text -----
  38.  
  39.  
  40. to a reduct of the final (√ç', E)-algebra
  41. relative to V. This uses a theorem due
  42. to Bergstra and Tucker (1983). If A is
  43. computable, then A is also isomorphic to the reduct of the initial (√ç', E)-algebra. 
  44. We also prove some results on congruences of finitely generated free algebras. We show that for every finite signature √ç, there are either countably many √ç con-gruences on the free √ç-algebra or else there is a continuum of such congruences. There are several necessary and sufficient conditions which separate these two cases. We introduce the notion of the Turing degree of a minimal algebra. Using the results above, we prove that there is a fixed one-sorted signature such that for 
  45.  
  46.  
  47.  
  48. -- part contents for background part 17
  49. ----- text -----
  50.  
  51.  
  52. every r.e. degree d, there is a finite set 
  53. E of √ç-equations such the initial (√ç, E)-algebra has degree d. There is a two-sorted signature √ç‚Äö and a single visible sort such that for every r.e. degree d there is a finite set E of √ç-equations such that the initial (√ç, E, V)-algebra is computable and the final (√ç, E,V)-algebra is cosemi-computable and has degree d.
  54.  
  55.  
  56.  
  57. -- part contents for background part 36
  58. ----- text -----
  59. 3.00